package jjn.round1;

import commons.TreeNode;

/**
 * @author Jjn
 * @since 2022/8/6 08:11
 */
public class LeetCode572_SubRoot {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        return isEqual(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    /**
     * 判断两棵树是否相同。
     *
     * @param p p
     * @param q q
     * @return boolean
     */
    private boolean isEqual(TreeNode p, TreeNode q) {
        if (p != null && q != null) {
            if (p.val != q.val) {
                return false;
            }
        }
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return isEqual(p.left, q.left) && isEqual(p.right, q.right);
    }
}
